1. Field of the Invention
The present invention relates to implementation of a Viterbi decoder in a wireless receiver, for example a IEEE 802.11a based Orthogonal Frequency Division Multiplexing (OFDM) receiver.
2. Background Art
Local area networks historically have used a network cable or other media to link stations on a network. Newer wireless technologies are being developed to utilize OFDM modulation techniques for wireless local area networking applications, including wireless LANs (i.e., wireless infrastructures having fixed access points), mobile ad hoc networks, etc.. In particular, the IEEE Standard 802.11a, entitled “Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: High-speed Physical Layer in the 5 GHz Band”, specifies an OFDM PHY for a wireless LAN with data payload communication capabilities of up to 54 Mbps. The IEEE 802.11a Standard specifies a PHY system that uses fifty-two (52) subcarrier frequencies that are modulated using binary or quadrature phase shift keying (BPSK/QPSK), 16-quadrature amplitude modulation (QAM), or 64-QAM.
Hence, the IEEE Standard 802.11a specifies an OFDM PHY that provides high speed wireless data transmission with multiple techniques for minimizing data errors.
A particular concern in implementing an IEEE 802.11 based OFDM PHY in hardware involves providing a cost-effective, compact device the can be implemented in smaller wireless devices. Hence, implementation concerns typically involve cost, device size, and device complexity.
For example, a forward error correction technique, known as convolutional coding with Viterbi decoding, has been used to provide encoded data to reduce bit errors. The purpose of forward error correction (FEC) is to improve the capacity of a wireless channel by adding some carefully designed redundant information to the data being transmitted through the channel. The process of adding this redundant information is known as channel coding. Convolutional coding and block coding are the two major forms of channel coding. Convolutional codes operate on serial data, one or a few bits at a time. Block codes operate on relatively large (typically, up to a couple of hundred bytes) message blocks. There are a variety of useful convolutional and block codes, and a variety of algorithms for decoding the received coded information sequences to recover the original data.
Convolutional codes are usually described using two parameters: the code rate and the constraint length. The code rate, k/n, is expressed as a ratio of the number of bits into the convolutional encoder (k) to the number of channel symbols output by the convolutional encoder (n) in a given encoder cycle. The constraint length parameter, K, denotes the “length” of the convolutional encoder, i.e. how many k-bit stages are available to feed the combinatorial logic that produces the output symbols. Closely related to K is the parameter m, which indicates how many encoder cycles an input bit is retained and used for encoding after it first appears at the input to the convolutional encoder. The m parameter can be thought of as the memory length of the encoder.
Viterbi decoding has the advantage that it has a fixed decoding time. It is well suited to hardware decoder implementation. But its computational requirements grow exponentially as a function of the constraint length K. In particular, the convolutional encoding of the data is accomplished using a shift register (composed of a prescribed number of flip flops) and associated combinatorial logic that performs modulo-two addition (e.g., XOR addition).
A significant characteristic of the convolutional encoding is that an input bit to the convolutional encoder (having, for example, two flip flops) has an effect on three successive pairs of output symbols. In particular, the state of a two-flip-flop register transitions to a prescribed new state in response to the next input; consequently, the output symbols of the convolutional encoder will follow a prescribed transition to one of two states (from a domain of 2(K-1) possible states) based on: (1) the state of the shift register, and (2) the input data. For example, in the case of a ½ convolutional encoder having 6 flip flops with a state of “19” (decimal) (i.e., 110010, left-most bit being the least significant bit and right-most bit being the most significant bit), an input bit having a value of “1” or “0” would cause the shift register to change to a state of “39” or “38”, respectively. Both the state transitions of the flip flops and the output symbols, also referred to as auto-correlation of the input data, can be characterized by respective output tables having 2(K-1) rows, and 2k columns, where K is the constraint length and k is the number of bits input to the encoder for each cycle.
The maximum size code word for IEEE 802.11a packets is 215 bits, and the ½ convolutional encoder (n=2, k=1) has 64 possible states based on a constraint length K=7 (i.e, based on the convolutional encoder having six (m=6) flip flops). In particular, given N bits for an input data stream, there are a possible 2N state transitions that may occur by the encoded data during the encoding of the data stream.
The Viterbi decoder determines the most likely state (i.e., encoded value) based on evaluating the sequence of received encoded code words. In other words, the Viterbi decoder determines, given an initial zero state of the encoder, the most probable value for a given encoder state relative to the respective transitions from other detected states; determining a state transition implicitly identifies the encoded data and vice versa. In summary, the Viterbi decoder, in response to receiving a pair of channel symbols, stores the received channel symbol pair and determines a distance metric (also referred to herein as an error metric) between the received channel symbol pair and the possible channel symbol pairs (which map to the respective possible encoder states). The mapping of an existing encoder state to a new state based on the input bit value is often illustrated using a Trellis diagram. As successive channel symbol pairs are received, the respective error metrics are applied to the prior possible encoder states to determine which of the prior possible encoder states become surviving predecessor states having the lowest respective accumulated errors.
The accumulated error value for each encoder state at each iteration (i.e., each instance of receiving a corresponding channel symbol pair) is stored in an accumulated metric table that specifies the accumulated error metric, for each possible encoder state, at each time instance. The surviving predecessor state for each encoder state at each iteration (i.e., each instance of receiving a corresponding channel symbol pair) is stored in a surviving state history table that specifies the surviving predecessor state, for each possible encoder state, at each time instance. Once the accumulated metric table and the surviving state history table has been populated with the respective values generated from stream of channel symbol pairs, a traceback algorithm recovers the original encoded stream based on tracing back from the state having minimum accumulated error in the accumulated metric table for a given instance (starting with the last time instance representing the last received channel symbol pair), to the prior state specified in the surviving state history table. Additional details of Viterbi decoding are described by Fleming, “A Tutorial on Convolutional Coding with Viterbi Decoding”, 2001, available on the World Wide Web at the exemplary web pages http://pw.netcom.com/˜chip.f/viterbi/tutorial.html, http://pw.netcom.com/˜chip.f/viterbi/algrhms.html and http://pw.netcom.com/˜chip.f/viterbi/algrthms2.html.
A particular problem of conventional Viterbi decoders involves the large number of computations required over the entire length of the convolutional encoded data stream. Since a code word can have a length of up to 4095 bytes, the storage of all state transitions during decoding of an entire code word could require at least 2-3 Mbytes of memory. One solution is to utilize a prescribed minimum number of instances (i.e., the traceback depth) to decode the first pair (i.e., two bits) of channel symbols. For example, the above-referenced Fleming document suggests a traceback depth of K×5 for Viterbi decoding a pair of channel symbols. Hence, a traceback decoding window having a depth of K×5 is used to decode a pair of convolutionally-encoded data bits.
However, even the use of a traceback decoding window of depth K×5 to decode a pair of convolutionally-encoded data bits may be insufficient for providing an economical implementation of an ODFM PHY capable of decoding the high data rates specified by IEEE 802.11a (e.g., 54 Mbps). In particular, use of a 25-instance window (50-bit window) (K=5) in a Viterbi decoder using a 40 MHz clock limits the output data rate to 3.2 Mbps (2/(25/40 MHz)=3.2 Mbps), assuming a single read port state history table.
Further, conventional implementations require complex addressing schemes to overcome memory access latencies caused by the substantially large number of data accesses required per decoding cycle. For example, assuming a backtracing window depth of D=30 instances, typically a Viterbi decoder, upon storing the first 30 pairs of samples, would retrieve the first 30 pairs of encoded data bits (e.g., pairs 0-29) to obtain the first pair of decoded data (e.g., for instance 0); the decoder would then retrieve the 30 pairs (e.g., pairs 1-30) needed for the next decoding sequence (e.g., instance 1). Hence, the generation of 30 pairs of decoded data would require 900 memory accesses.